/*
 * @lc app=leetcode.cn id=113 lang=cpp
 *
 * [113] 路径总和 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// #include <numeric>  //算容器类元素和可用accumulate函数
// #include <vector>

// struct TreeNode
// {
//   int val;
//   TreeNode* left;
//   TreeNode* right;
//   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution
{
 public:
  // 全局变量
  vector<vector<int>> ans;
  vector<int> path;

  vector<vector<int>> findPath(TreeNode* root, int sum)
  {
    dfs(root, sum);
    return ans;
  }

  void dfs(TreeNode* root, int sum)
  {
    if (!root) return;  // 如果当前节点是空的，那么他就不是叶子节点，直接return完事

    path.push_back(root->val);
    sum -= root->val;
    if (!root->left && !root->left && !sum)
      ans.push_back(path);  // 若访问到叶子节点(前两个判断)且0==sum, 此时路径满足放进ans

    dfs(root->left, sum);
    dfs(root->right, sum);
    // 把path放进ans后需要清空给其他分支，同时在清空之上要递归深搜左右子分支
    path.pop_back();
  }
};

/*
class Solution
{
 public:
  vector<vector<int>> pathSum(TreeNode* root, int sum) {}

 private:
  void path_sum(TreeNode* root, vector<int>& path, vector<vector<int>>& result, int gap)
  {
    if (root == nullptr)
      return;  // 递归出口

    else
    {
      path.push_back(root->val);  // 存储结点元素到path
    }

    if (nullptr == root->left && nullptr == root->right)  // 叶子结点时push path到结果向量中
    {
      //
如果该path和为sum则push到结果向量中（这里用sum累减路径上的元素，得到gap与路径上最后一个元素比较，节省时间，如果得到path再accumulate，则会造成不同路径间的重复计算）
      if (gap == root->val) result.push_back(path);

      // return; //递归出口，到叶结点后退出，（不能写这句，还需运行到结尾进行pop）
    }

    path_sum(root->left, path, result, gap - root->val);  // 沿深度方向遍历
    path_sum(root->right, path, result, gap - root->val);
    path.pop_back();  // 删除最后一个元素，腾出空间(本函数中只push了一次，故只需pop一次,
                      //
这个pop只在遍历到叶子节点起作用，此时上面的两个path_sum函数不起作用，为另一个分支腾出空的vector<int>path)
  }
};
*/
// @lc code=end
